package problem_everyday;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class D2025_06_29_P1498 {
    /*
    *   求nums的子序列的个数
    *   要求子序列的最小元素和最大元素的和 <= target
    *   个数比较大，取模10^9 + 7
    *
    *   1 <= nums.lenth <= 10^5
    *   1 <= nums[i], target <= 10^6
    * */

    /*
    * 如果我已经确定了最小和最大元素组合
    *   可以再次扫描 整个数组，将位于这个区间的加入到子序列
    * */

    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        int[] count = new int[nums.length + 1];
        int left_num = 0;
        int i = nums.length - 1;
        int max_count = 0;
        for(; i>=0 && nums[i] > target / 2; i--){
            if(nums[i] > target) continue;
            // 找到第一个满足该关系的值
            while(left_num <= i && nums[left_num] + nums[i] <= target) left_num ++;
            if(left_num > 0){
                // 如果选择第 left_num 个作为左边界，则有 i - left_num - 1 个中间元素
//                for(int j=1; j<=left_num; j++){
//                    int internal_num = i - j; // 2 ^ internal_num
//                    count[internal_num] ++;
//                    max_count = Math.max(max_count, internal_num);
//                }
                /*优化：使用次幂求和公式 2^max + .. + 2^min = 2 ^(max+1) - 2 ^ min */
                max_count = Math.max(max_count, i);
                count[i] ++ ;
                count[i-left_num] --;
            }
        }
        for(;i>=0; i--){
            count[i] ++;
            max_count = Math.max(max_count, i);
        }
        long mask = 1;
        int mod_num = ((int) 1e9)  + 7;
        long res = count[0];
        for(int j=1; j<=max_count; j++){
            mask = mask * 2  % mod_num;
            if(count[j]==0) continue;
            res = res + ( mask * count[j] % mod_num);
            res = res % mod_num;
        }
        return (int) res;
    }

    public static void main(String[] args){
        int[] nums = {3,5,6,7};
        int target = 9;
        D2025_06_29_P1498 p = new D2025_06_29_P1498();
        int res = p.numSubseq(nums, target);
        System.out.println(res);
    }
}
